首页 > 试题广场 >

二分查找-I

[编程题]二分查找-I

热度指数：222399 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请实现无重复数字的升序数组的二分查找

给定一个元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

数据范围： $0 \le len(nums) \le 2\times10^5$ ，数组中任意值满足 $|val| \le 10^9$

进阶：时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$

示例1

输入

[-1,0,3,4,6,10,13,14],13

输出

说明

13 出现在nums中并且下标为 6

示例2

输入

[],3

输出

-1

说明

nums为空，返回-1

示例3

输入

[-1,0,3,4,6,10,13,14],2

输出

-1

说明

2 不存在nums中因此返回 -1

备注:

数组元素长度在[0,10000]之间
数组每个元素都在 [-9999, 9999]之间。

算法知识视频讲解

Python 3

pzq

# 递归的写法
class Solution:
    def find(self, nums, ind1, ind2, target):
        ind = (ind1 + ind2) // 2
        # 终止条件
        if nums[ind] == target:
            return ind
        if ind in [ind1, ind2]: # 此时说明不存在
            return -1
        # 查找数据在右边
        if target > nums[ind]:
            return self.find (nums, ind, ind2, target)
        # 查找数据在左边
        if target < nums[ind]:
            return self.find (nums, ind1, ind, target)

    def search(self , nums: List[int], target: int) -> int:
        # 二分查找
        if nums == []:
            return -1
        return self.find(nums, 0, len(nums), target)

发表于 2023-05-19 01:33:38 回复(0)

Python 3

牛客863195265号

题目给出的测试例子有数组长度为0的情况，因此在用二分法时应设定区间是左闭右开的。

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        left , right = 0 , len(nums)
        while left < right :
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

发表于 2022-09-14 14:53:36 回复(0)

Python 3

小Rzz

class Solution:
def search(self , nums: List[int], target: int) -> int:
# write code here
if target in nums:
return nums.index(target)
else:
return -1

发表于 2022-08-29 11:17:31 回复(0)

Python 3

浪小白er

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        left = 0 #设置左指针
        right = len(nums) - 1   #设置右指针
        while left <= right:    #候选区有值的情况
            mid = (left+right)//2
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                left = mid + 1  #目标值大于中间值，左指针移动至中间值后一位
            else:
                right = mid - 1 #目标值小于中间值，左指针移动至中间值前一位
        else:
            return -1   #没有目标值的情况

发表于 2022-08-25 13:55:14 回复(0)

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        l=0.0
        r=len(nums)-1
        while l<=r:
            mid=int(0.5*(l+r))
            #print(mid)
            if nums[mid]==target:
                return mid
            if nums[mid]<=target:
                l=mid+1
            else:
                r=mid-1
        return -1

发表于 2022-08-18 19:57:18 回复(0)

Python 3

杨枝甘露yyds

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if not nums: return -1
        if len(nums)==1 and nums[0]==target: return 0
        i,j =0,len(nums)-1
        while i<j : 
            if nums[i] < target:
                i += 1
            elif nums[j] > target:
                j -= 1
            if nums[i] == target:
                return i
            elif nums[j] == target:
                return j
        return -1

发表于 2022-07-26 03:07:31 回复(0)

Python 3

风软一江山

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        if len(nums) < 1:
            return -1
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = int((left+right) / 2)
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

发表于 2022-07-19 14:08:37 回复(0)

Python 3

来牛客玩玩

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if not nums:
            return -1
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid+1
            else:
                r = mid-1
        return -1

发表于 2022-07-09 06:44:52 回复(0)

Python 3

从8开始倒车

每次比较之后，挪动左右坐标时，不能直接等于中间坐标，而是中间坐标±1，不然就会进行死循环。

发表于 2022-06-13 23:13:38 回复(0)

Python 3

0828tian

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        
        while left <= right:
            middle = (left+right) // 2
            if nums[middle] == target:
                return middle
            if nums[middle] < target:
                left = middle + 1
            else:
                right = right - 1
        return -1

发表于 2022-06-09 17:48:29 回复(0)

Python 3

Vivimore

class Solution:
    # 非递归版
    # 时间复杂度：O(logn)  空间复杂度：O(1)
    def search(self , nums: List[int], target: int) -> int:
        first = 0
        last = len(nums) - 1
        while first <= last:
            mid = (first + last) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                last = mid - 1
            else:
                first = mid + 1
        return -1

发表于 2022-05-16 10:04:17 回复(0)

Python 3

JianYue

class Solution:
def search(self , nums: List[int], target: int) -> int:
left, right = 0, len(nums) -1
while right >= left:
mid = (left + right) // 2
if nums[mid] > target:
right=mid-1
elif nums[mid] < target:
left=mid+1
else:
return mid
return -1

发表于 2022-05-14 18:14:55 回复(0)

Python 3

尘一心

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return -1
        left, right = 0, len(nums)
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

发表于 2022-05-05 14:32:05 回复(0)

Python 3

yifan1997

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        low = 0
        high = len(nums)-1
        while low<=high:
            mid = (high-low)//2+low
            num = nums[mid]
            if num == target:
                return mid
            elif num>target:
                high = mid -1
            else:
                low = mid+1
        return -1

发表于 2022-04-29 00:31:20 回复(0)

Python 3

danspace

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        l, r = 0, len(nums)-1        
        while l <= r:
            i = (l+r)//2
            if target == nums[i]:
                return i
            elif target < nums[i]:
                r = i-1
            else:
                l = i+1
        return -1

发表于 2022-04-24 11:40:11 回复(0)

Python 3

一只兔子的奇幻之旅

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        if len(nums)==0:
            return -1
        return self.find(nums,target)
    def find(self,arr,target):
        low,high=0,len(arr)
        while low<=high:
            mid=low+(high-low)//2
            if arr[mid]<target:
                low=mid+1
            elif arr[mid]>target:
                high=mid-1
            else:
                return mid
        return -1

发表于 2022-04-23 22:53:04 回复(0)

Python 3

今天不做咸鱼

class Solution:
def search(self , nums: List[int], target: int) -> int:
# write code here
z = 0
for i in range(len(nums)):
if nums[i] == target:
z=z+1
return i
if z == 0:
return -1

发表于 2022-04-16 20:52:12 回复(0)

提交观点

问题信息

二分

上传者：牛客301499号

难度：

27条回答 372收藏 3882浏览

通过挑战的用户

查看代码

TV体育

2023-03-05 10:21:37
随机昵称都有什...

2023-02-17 18:15:42
His步步

2023-01-19 13:25:18
lightzc

2022-12-25 00:28:03
Echo_paul

2022-11-02 22:53:01

二分查找-I

输入

输出

说明

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题